import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class test768 {
    public int maxChunksToSorted(int[] arr) {
        int[] arrCopy = Arrays.copyOf(arr, arr.length);
        Arrays.sort(arrCopy);
        Map<Integer, Integer> numberIndexMap = new HashMap<>();
        int indexForArr = 0, maxIndexForArrCopy = 0, count = 0;
        while(indexForArr < arr.length){
            int cur = arr[indexForArr];
            int orderIndex = numberIndexMap.getOrDefault(cur, findLocation(arrCopy, 0, arr.length - 1, cur));
            numberIndexMap.put(cur, orderIndex + 1);
            maxIndexForArrCopy = Math.max(maxIndexForArrCopy, orderIndex);
            if(maxIndexForArrCopy == indexForArr){
                count ++;
            }
            indexForArr ++;
        }
        return count;
    }

    public int findLocation(int[] arr, int left, int right, int target){
        if(left > right){
            return -1;
        }
        int midIndex = (left + right) / 2;
        if(arr[midIndex] == target){
            while(midIndex >= 0 && arr[midIndex] == target){
                midIndex --;
            }
            return ++midIndex;
        }
        else if(arr[midIndex] > target){
            return findLocation(arr, left, midIndex - 1, target);
        }
        else{
            return findLocation(arr, midIndex + 1, right, target);
        }
    }

    @Test
    public void test(){
        maxChunksToSorted(new int[]{5,4,3,2,1});
    }
}
